package com.zklh.leetcode.tree.middle;

import com.zklh.leetcode.tree.model.TreeNode;

/**
 * @author ：tong nan
 * @date ：Created in 2021/4/28 16:11
 * @description ：根据中序和后序遍历结果进行构建二叉树
 * @modifiedBy ：
 */
public class BinaryTreeByInorderAndPostorderConstructor {


    public TreeNode construct(int[] inorderResult, int[] postorderResult) {

        return construct(inorderResult, postorderResult, 0, inorderResult.length-1, 0, postorderResult.length-1);
    }

    private TreeNode construct(int[] inorderResult, int[] postorderResult, int inLeft, int inRight, int postLeft, int postRight) {

        if (inLeft > inRight) {
            return null;
        }

        TreeNode now = new TreeNode(postorderResult[postRight]);

        // 中序遍历的中间节点
        int inMiddle = inLeft;
        int tempIn = inLeft;
        while (tempIn <= inRight) {
            if (now.val == inorderResult[tempIn]) {
                inMiddle = tempIn;
                break;
            }
            tempIn++;
        }
        int leftTreeLength = inMiddle - inLeft;
        now.left = construct(inorderResult, postorderResult, inLeft, inMiddle-1, postLeft, postLeft+leftTreeLength-1);
        now.right = construct(inorderResult, postorderResult, inMiddle+1, inRight, postLeft+leftTreeLength, postRight-1);

        return now;
    }

    public static void main(String[] args) {
        BinaryTreeByInorderAndPostorderConstructor constructor = new BinaryTreeByInorderAndPostorderConstructor();
        TreeNode node= constructor.construct(new int[]{9,3,15,20,7}, new int[]{9,15,7,20,3});
    }

}
